package leetcode.code986;

import java.util.ArrayList;
import java.util.List;

public class Solution1 extends Solution986 {

	@Override
	public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
		if (firstList == null || secondList == null || firstList.length == 0 || secondList.length == 0)
			return new int[][] {};
		int fx = firstList.length;
		int sx = secondList.length;
		List<int[]> list = new ArrayList<>();
		int f = 0;
		int s = 0;
		while (f < fx && s < sx) {
			int fl = firstList[f][0];
			int fr = firstList[f][1];
			int sl = secondList[s][0];
			int sr = secondList[s][1];
			if ((sl <= fl && fl <= sr) && (sl <= fr && fr <= sr)) {
				// f在s里
				list.add(new int[] { fl, fr });
				f++;
			} else if ((sl <= fl && fl <= sr) && (fr > sr)) {
				// f在后s在前
				list.add(new int[] { fl, sr });
				s++;
			} else if ((fl < sl) && (sl <= fr && fr <= sr)) {
				// f在前s在后
				list.add(new int[] { sl, fr });
				f++;
			} else if (fl < sl && fr > sr) {
				// f在s外
				list.add(new int[] { sl, sr });
				s++;
			} else {
				if (fl < sl) {// f在前，f废了
					f++;
				} else {// 否则s废了
					s++;
				}
			}
		}
		int[][] result = new int[list.size()][2];
		for (int i = 0; i < list.size(); i++) {
			result[i] = list.get(i);
		}
		return result;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
